package com.itheima.datastructure.heap;

import java.util.Comparator;
import java.util.PriorityQueue;

public class E04Leetcode295_2 {

    public void addNum(int num){
        if(left.size()==right.size()){
            right.offer(num);
            left.offer(right.poll());
        }else{
            left.offer(num);
            right.offer(left.poll());
        }
    }

    public double findMedian(){
        if(left.size()==right.size()){
            return (left.peek()+right.peek())/2.0;
        }else{
            return left.peek();
        }
    }

    //大顶堆
    private PriorityQueue<Integer> left=new PriorityQueue<>(
            (a,b)->Integer.compare(b,a)
    );
    //小顶堆
    private PriorityQueue<Integer> right=new PriorityQueue<>();

    public static void main(String[] args) {
        E04Leetcode295_2 test = new E04Leetcode295_2();
        test.addNum(1);
        test.addNum(2);
        test.addNum(3);
        test.addNum(7);
        test.addNum(8);
        test.addNum(9);
        System.out.println(test.findMedian());
        test.addNum(10);
        System.out.println(test.findMedian());
        test.addNum(4);
        System.out.println(test.findMedian());
    }

}
